package leetcode;

import java.util.Stack;

/**
 * 84. 柱状图中最大的矩形
 * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
 * 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
 * 示例:
 * 输入: [2,1,5,6,2,3]
 * 输出: 10
 */

public class problems_084 {

    public static void main(String[] arge) {
        System.out.println(new Solution().largestRectangleArea(new int[]{2,1,5,6,2,3}));
    }
    static class Solution {
        public int largestRectangleArea(int[] heights) {
            int length = heights.length;
            Stack<Integer> stack = new Stack<>();
            int maxArea = 0;
            for (int i = 0; i <= length; i++) {
                int h = (i == length ? 0 : heights[i]);
                //如果栈是空的，或者当前柱子的高度大于等于栈顶元素所对应柱子的高度,
                //直接把当前元素压栈
                if (stack.isEmpty() || h >= heights[stack.peek()]) {
                    stack.push(i);
                } else {
                    int top = stack.pop();
                    int area = heights[top] * (stack.isEmpty() ? i : i - 1 - stack.peek());
                    maxArea = Math.max(maxArea, area);
                    i--;
                }
            }
            return maxArea;
        }
    }

//    static class Solution {
//        public int largestRectangleArea(int[] heights) {
//            if (null == heights || heights.length == 0) return 0;
//            int ret = 0;
//            for (int i = 0; i < heights.length; i++) {
//                ret = Math.max(ret, findNum(heights, i));
//            }
//            return ret;
//        }
//        // 取得面积
//        private int findNum(int[] heights, int index) {
//            int height = heights[index];
//            int start = index;
//            int end = index;
//            while (start - 1 >= 0 && heights[start - 1] >= height) start--;
//            while (end + 1 < heights.length && heights[end + 1] >= height) end++;
//            return height * (end - start + 1);
//        }
//    }


//    static class Solution {
//        public int largestRectangleArea(int[] heights) {
//            if (null == heights || heights.length == 0) return 0;
//            int start = 0;
//            int end = heights.length - 1;
//            int ret = 0;
//            while (start < end) {
//                //
//                ret = Math.max(ret, findNum(heights, start, end));
//                System.out.println("指针：" + start + "_" + end + ", 面积：" + ret);
//                // 指针切换
//                if (heights[start + 1] > heights[start]) {
//                    start++;
//                } else if (heights[end - 1] > heights[end]) {
//                    end--;
//                } else if(heights[start] >= heights[end]){
//                    end--;
//                } else if(heights[start] < heights[end]){
//                    start++;
//                } else {
//                    start++;
//                    end--;
//                }
//            }
//            return ret;
//        }
//
//        // 取得面积
//        private int findNum(int[] heights, int start, int end) {
//            int height = Integer.MAX_VALUE;
//            for (int i = start; i <= end; i++) {
//                height = Math.min(height, heights[i]);
//            }
//            return height * (end - start);
//        }
//    }
}
